Module Overview

[Lecture on 1.3]

You are expected to attend all lectures - they are not recorded and there will be important information not included in the emails.

Textbook

"Computer Networks, 5th ed"
Prentice Hall 2010
Andrew S. Tanenbaum and Wetherall

Entirely optional - notes should be sufficient.

Problem Sets

Problem sets will be given out
They are not graded or handed up, they're practice

Assessments

Four in-class tests

Provisional dates:
Test 1: Friday October 4th (11 am) 10% (Week 4)
Test 2: Friday October 25th (11 am) 20% (Week 7)
Test 3: Friday November 15th (11 am) 30% (Week 10)
Final Exam (on-campus with laptop) in the exam period - 40%

We'll get letter grades for each one (I think ?) then he uses the calculation points system for final grades.

Switching

Motivation

Two extreme topologies:
Mesh vs. central
Pasted image 20240911102304.png Pasted image 20240911102314.png

Mesh obviously requires way too many links
Central has drawbacks:

Single point of failure (router)
Single link failure cuts off a node
Enormous traffic at router node
Potentially wasteful if lots of communications are to 'nearby' devices

So we'll need something inbetween

So what is the optimum number of switches?
Limit on scale of a single switch.
Reliability of a single switch is also limited.

Two kinds of link:

User to switch ('access link')
Switch to switch

You get topologies that could look like this:

Example

In Ireland there are 5 million phones
Connected by about 10k mobile masts
These are connected by ~100 major switches
So
500 phones per mast
50,000 phones per major switch
Switches connected through a backbone network (backbone could be as few as 5-6 massive switches)

Switch Considerations

How to measure performance?
Cost to build switch
Number of inputs/outputs
Can all possible connections be switched?
How does the switch grow with connection count
Functionality and technology of the switch (not on this module)

Strictly Non-Blocking Switch

Device that can connect any of n inputs to any of m outputs
- Provided the output is not busy
- 1-1 connections only
This is called a 'strictly non-blocking switch'
- i.e. any connection can be made (if they're free), so it should never block a connection

Switch Structure - Ports

Pasted image 20240911103537.png

Non-Strict Non-Blocking Switch

Weaker alternatives to strictly non-blocking switch
Non-blocking with Rearrangement:
- Allows any connection to be made, but may require other existing connections be rearranged
Non-Blocking with Connection Packing Rule
- Non-blocking as long as the connections are put up in a particular order

Some blocking may be acceptable if it's small enough.

Crosspoints

Switching gets much more difficult with scale - we'll look at generally 1000 ports
Input/output is a bit of an abstract idea, in reality they are usually one and the same
Crosspoint: connects an input to an output.
- We often want to minimise how many we need as they may be expensive

Basic analogue crosspoint:
Pasted image 20240911103957.png

Crossbar Switch

Pasted image 20240911104047.png
Each crosspoint here can be enabled to link the two wires passing under it

Consider that this switch has 512 possible configurations, the vast majority of which are not very useful. This may suggest that there are too many crosspoints ( crosspoints)

Modern crosspoints are electronic transistors
See also: Time Switching

[End of lecture on 1.3]
[Lecture on 1.5]

Switch Design

Usually we will look at square switches (equal inputs and output)
Want to minimise the number of crosspoints C() as each one has an associated cost
Multi-stage switches are one option
Clos Networks are the key idea

Clos Switch

Clos Networks

Three stage switch
Notice the switches on the right have transposed dimensions from the ones on the left
sometimes
Strictly non-blocking

input switches (each is an -> crossbar)
center switches (each is -> crossbar)
output switches (each is a -> crossbar)
You can apply this idea recursively, turning each of the center stage switches (crossbars) into its own Clos network

Number of crosspoints:

Input stage:
Output stage: Same again
Center stage:

Noting that , you get
Total:

Optimal value is and giving

For , this beats a crossbar.

You'll need to round up or down to an integer usually - generally you should attempt both up and down and see which performs better.

Calculate and round it up, then calculate and always round that up (so you have enough ports)
Then try again but round down

Recursion

The middle stage has the most switches, so we can eliminate some by replacing that with another 3-stage clos switch, overall yielding a 5-stage switch.

There is an optimal number of stages for a given value of N

Generally you'll only need 3 or 5 stages, it's only worth implementing more for extremely large switches

Time vs. Space Switching

Time switching is cheaper than space switching and well-suited to digital media
Space switching cannot be fully avoided, but minimised

Typical switch may use Time-space-time layers.

Moore Switch

Non-blocking only with a call packing rule
This switch needs certain rules to pack the calls or else it could be blocking
Packing Rule: Use the most crowded center stage switch if you have a choice at all
Three-stage switch with similar interconnections to Clos switch, except the middle layer is all 2x2 crossbars
Not very useful as it has more crosspoints than a full crossbar

CSS: Center-State Switch

Proof of Non-Blocking with Rule

Each 2x2 CSS has seven possible states:

Empty
'Uncrossed' states:
- Top-top
- Bottom-bottom
- Full, uncrossed
'Crossed' states:
- Top-bottom
- Bottom-top
- Full, crossed
Number these states 0-6

Let be the number of center stage switches in state
Let be the number of css in use when in state y
(CSS: Center-stage switch)

Prove that:
(eq 1)
Prove that:
(eq 2)
(eq 3)

Use induction

Slepian Switch

Blocking with any call packing rule
but non-blocking with rearrangement
switch with no expansion or compression